# This is a packet of sort algorithms.

import random
import math

# 1. merge sort.
def Union(L1, L2):
    '''
    Union two ordered list.
    '''
    i = 0
    j = 0
    L = []
    while i < len(L1) and j < len(L2):
        if L1[i] <= L2[j]:
            L.append(L1[i])
            i += 1
        elif L1[i] > L2[j]:
            L.append(L2[j])
            j += 1
        
    L = L + L1[i:] + L2[j:]
    return L

def Merge_sort(L,p,r):
    '''
    Input:
    - L: a unordered list
    - p: the start index
    - r: the end index
    Output:
    - L: a ordered list.
    '''
    if p > r:
        print('Error input.')
        return L
    if r - p == 0:
        return [L[p]]
    if r - p == 1:
        if L[r] < L[p]:
            L[r], L[p] = L[p], L[r]
        return [L[p], L[r]]
    q = int((p + r) / 2)
    left = Merge_sort(L,p,q)
    right = Merge_sort(L,q+1,r)
    return Union(left,right) 


# 2. quick_sort
def Naive_partition(L,p,r):
    pivot = L[r] # 主元为最后一个
    i = p-1
    for j in range(p,r):
        if L[j] <= pivot: 
            i += 1
            L[i], L[j] = L[j], L[i]
    return i+1

def Naive_quick_sort(L,p,r):
    '''
    Input: 
    - L: A unordered list.
    - p: the first index.
    - r: the last index.
    Output:
    - L: A order list.
    '''
    if p <= r:
        q = Naive_partition(L,p,r)
        left = Naive_quick_sort(L,p,q-1)
        right = Naive_quick_sort(L,q, r-1)
        return left + [L[r]] + right
    return []

def Random_partition(L,p,r):
    index = random.randint(p,r)
    L[index], L[r] = L[r], L[index]
    pivot = L[r]
    i = p - 1
    for j in range(p,r):
        if L[j] <= pivot:
            i += 1
            L[i], L[j] = L[j], L[i]
    return i+1

def Random_quick_sort(L,p,r):
    if p <= r:
        q = Random_partition(L,p,r)
        left = Random_quick_sort(L,p,q-1)
        right = Random_quick_sort(L,q,r-1)
        return left + [L[r]] + right
    return []


# 3. heap_sort
def Max_heapify(L, i):
    '''
    Insert ith node and maintain  max heap.
    Input:
    - L: A list. And the left and right subtree of i is max heap.
    - i: the index.
    
    Output:
    - L: A max heap.
    '''
    l = 2*i + 1
    r = 2*i + 2
    greatest_index = None
    if l < len(L) and L[l] > L[i]:
        greatest_index = l
    else:
        greatest_index = i
    if r < len(L) and L[r] > L[greatest_index]:
        greatest_index = r
    if greatest_index != i:
        L[i], L[greatest_index] = L[greatest_index], L[i]
        Max_heapify(L, greatest_index)
        
def Build_Max_Heap(L):
    '''
    Construct the max heap.
    Input:
    - L: A unordered list.
    Output:
    - L: A max heap.
    '''
    n = len(L)
    for i in range(math.floor(n/2),-1,-1): # range 的区间是 [start, stop)
        Max_heapify(L,i)
        
def Heap_sort(L):
    Build_Max_Heap(L)
    for i in range(len(L)-1,-1,-1):
        L[0],L[i] = L[i],L[0] 
        t = L[0:i] # 区间是 [0, i)
        Max_heapify(t,0)
        L[0:i] = t
    return L
        
        
# 4. Insert_sort
def Insert_sort(L,p,r):
    '''
    Insert sort.
    Input:
    - L: A unordered list.
    - p: the first index.
    - r: the last index.
    Output:
    - L: A order list.
    '''
    for i in range(p+1,r+1):
        for j in range(i,p,-1):
            if L[j] < L[j-1]:
                L[j], L[j-1] = L[j-1], L[j]
            else:
                break
    return L


# 5. Bucket_sort
def Bucket_sort(L,n,a,b):
    '''
    Input:
    - L: the unordered list.
    - n: the number of buckets.
    - a: the lower bound.
    - b: the upper bound.
    Output:
    - L: the ordered list.
    '''
    bucket = [[] for i in range(n)]
    for i in range(len(L)):
        bucket[(L[i] - a) * n // (b - a )].append(L[i])
    for i in range(n):
        # 对每个 bucket 进行排序
        bucket[i] = Merge_sort(bucket[i],0,len(bucket[i])-1)
    L = [a for b in bucket for a in b]
    return L

# 6. Counting_sort
def Counting_sort(L,k):
    '''
    Input:
    - L: the unordered list.
    - k: the upper bound.
    Output:
    - List: the ordered list.
    '''
    B = [0 for i in range(k)]
    for i in range(len(L)):
        B[L[i]] += 1
    for i in range(1,len(B)):
        B[i] = B[i] + B[i-1]
    List = [0 for i in range(len(L))]
    for i in range(len(L)-1,-1,-1):
        List[B[L[i]]-1] = L[i]
        B[L[i]] -= 1
    return List

# 7. Radix_sort
def Radix_sort(L, d=256):
    for i in range(d):
        bucket = [[] for i in range(10)] # 十进制 所以用 十个桶进行排序
        for j in L:
            bucket[j // (10 ** i) % 10].append(j)
        L = [a for b in bucket for a in b]
    return L


